package com.leetcode.algorithm.y22.m05;

/**
 * 322. 零钱兑换 
 * https://leetcode.cn/problems/coin-change/
 * 
 * @author jie.deng
 *
 */
class Question0322Solution02 {
	
	public int coinChange(int[] coins, int amount) {
		// 动态规划
		// minCnts[i]表示凑成总金额i所需的最少的硬币个数
		int[] minCnts = new int[amount + 1];

		// 初始状态
		minCnts[0] = 0;
		for (int idx = 1; idx <= amount; idx++) {
			int minCnt = Integer.MAX_VALUE;
			for (int coin : coins) {
				int prevIdx = idx - coin;
				if (prevIdx >= 0 && minCnts[prevIdx] != Integer.MAX_VALUE) {
					// 状态转移方程
					minCnt = Math.min(minCnts[prevIdx] + 1, minCnt);
				}
			}
			minCnts[idx] = minCnt;
		}
		return minCnts[amount] == Integer.MAX_VALUE ? -1 : minCnts[amount];
	}
	
}